package sort;

/**
 * 插入排序
 */

public class InsertSort {
    public static void insertSort1(int [] arr) {
        /*//外层控制次数，因为0~0这次排序已经完成，所以直接从1开始，我们只需要跑length-1趟即可完成算法
        //同时i指向新来的、待插入排序的数
        //因此是从1开始，直到最后一位
        for (int i = 1; i < arr.length; i++) {
            //currNumIndex表示当前待插入的数的下标（位置）
            int currNumIndex = i;
            //在摸牌式插入进行时，currNum会不断向前移动
            //若是currNum前面还有数字，且currNum前一个数大于currNum，则交换位置
            while (currNumIndex - 1 >= 0 && arr[currNumIndex-1] > arr[currNumIndex]){
                //交换元素
                swap(arr,currNumIndex-1,currNumIndex);
                //当前新插入元素左移
                currNumIndex--;
            }
        }*/

        /**
         * 感觉插入排序像是反向版的冒泡排序。
         * sortedIndex前面的部分都是排好序的部分，sortedIndex要找到自己应有的位置，插入到前面去。
         * 当然是冒泡一般地插进去
         */
        //边界判断
        if (arr.length < 2 && arr == null){
            return;
        }

        //i就表示待排序的位置
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j > 0 ; j--) {
                if (arr[j]<arr[j-1]){
                    swap(arr,j,j-1);
                }else {
                    break;
                }
            }
        }
    }

    public static void insertSort2(int [] arr) {
        /**
         * 此乃写法一的改进版
         */
        for (int newNumIndex = 1; newNumIndex < arr.length; newNumIndex++) {
            /**
             * pre指向当前等待新插入的数的前一个位置
             * 若是pre没出界，且新等待插入数字的前一位大于等待输入数
             * 交换
             */
            for (int pre = newNumIndex - 1 ; pre >= 0 && arr[pre] > arr[pre+1] ; pre--) {
                swap(arr,pre,pre+1);
            }
        }
    }

    public static void printArray(int [] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void swap(int [] arr,int i,int j){
        int temp=arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int [] array = new int[]{5,6,8,9,3};
        insertSort1(array);
        printArray(array);
    }
}
